package org.example.Soution003;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class DynamicProgrammingLargestBracketArray {
    public static void main(String[] args) {
        DynamicProgrammingLargestBracketArray dp = new DynamicProgrammingLargestBracketArray();
        String s="";
        System.out.println(dp.longestValidParentheses(s));
    }

    public int longestValidParentheses(String s) {
        if(s.isEmpty() ||s.length()==1) return 0;
        char[] chars = s.toCharArray();
        int n=chars.length;
        List<Integer> list=new ArrayList<>();
        int[] maxNow=new int[n];
        int[] res=new int[n];

        for(int i=0;i<n;i++){
            if(list.isEmpty()&& chars[i]==')'){
                maxNow[i]=0;res[i]=i-1>=0?res[i-1]:0;
                continue;
            }
            int length=list.size();
            if(chars[i]=='('){
                list.add(i);
                maxNow[i]=0;
                res[i]=i-1>=0?res[i-1]:0;
            }else{
                int tmp=list.remove(length-1);
                maxNow[i]=(i-tmp+1)+ (tmp-1>=0?maxNow[tmp-1]:0);
                res[i]=Math.max(res[i-1],maxNow[i]);
            }
        }
//        System.out.println(Arrays.toString(maxNow));
//        System.out.println(Arrays.toString(res));
        return res[n-1];
    }
}
